package hot100;

import java.util.Arrays;

public class nextPermutation2 {
    public static void nextPermutation(int[] nums) {

        int n = nums.length - 1;
        int min = n;
        int index = n;

        // 开始寻找右边比左边大的2个数 ，右边的数下标为index
        while (  index > 0&&nums[index - 1] >= nums[index]) {
            index--;
        }
        // 从右往左，找到第一个大于index-1的数
        while( index > 0&&nums[index-1] >= nums[min]) {
            min--;
        }
        // 如果idex = 0，此时已经是最大的，需要重新排序
        if (index == 0) {
            Arrays.sort(nums);

        } else {

            // 交换最小的数和 左边的数
            int tem = nums[min];
            nums[min] = nums[index - 1];
            nums[index - 1] = tem;

            // 开始对index-1 之后数组进行升序排序
            Arrays.sort(nums, index, n+1);
        }

    }
}
